from collections import deque

class GMUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}          # {object_id: (size, will_visit)}
        self.lru_queue = deque() # 维护访问顺序

    def access_object(self, obj_id, obj_size, will_visit):
        # 如果对象已在缓存中，更新LRU位置
        if obj_id in self.cache:
            self.lru_queue.remove(obj_id)
            self.lru_queue.appendleft(obj_id)
            return True  # 命中

        # 如果缓存未满，直接插入
        if len(self.cache) < self.capacity:
            self.cache[obj_id] = (obj_size, will_visit)
            self.lru_queue.appendleft(obj_id)
            return False  # 未命中但插入成功

        # 缓存已满，执行替换策略
        self.replace_object(obj_id, obj_size, will_visit)
        return False

    def replace_object(self, obj_id, obj_size, will_visit):
        # 替换策略逻辑
        if will_visit == 1:
            if obj_size < 0.3 * self.capacity:
                position = 0  # 插入头部
            else:
                position = len(self.lru_queue) // 2  # 插入中部
        else:
            position = len(self.lru_queue)  # 插入尾部

        # 淘汰尾部对象
        if position == len(self.lru_queue):
            removed_id = self.lru_queue.pop()
            del self.cache[removed_id]
        else:
            # 自定义插入逻辑（此处简化为淘汰最后一个）
            removed_id = self.lru_queue.pop()
            del self.cache[removed_id]

        # 插入新对象
        self.cache[obj_id] = (obj_size, will_visit)
        self.lru_queue.insert(position, obj_id)